home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / c / library / dos / diverses / leda / incl / partitio.h < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  2.4 KB  |  113 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  partition.h
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17.  
  18. #ifndef PARTiTIONH
  19. #define PARTITIONH
  20.  
  21. //------------------------------------------------------------------------------
  22. // partition   (union find)
  23. //
  24. // Stefan Naeher  (1989)
  25. //------------------------------------------------------------------------------
  26.  
  27. #include <LEDA/basic.h>
  28.  
  29.  
  30. class partition_node {
  31.  
  32. friend class partition;
  33.  
  34. partition_node* father;
  35. partition_node* next;
  36. int size;
  37. ent info;
  38.  
  39. public:
  40.  
  41. partition_node(ent x, partition_node* n)  
  42. { 
  43.   father=0; size=1; info=x; next = n; 
  44.  }
  45.  
  46. OPERATOR_NEW(4)
  47. OPERATOR_DEL(4)
  48.  
  49. };
  50.  
  51.  
  52. // a partition item is a pointer to a partition node:
  53.  
  54. typedef partition_node* partition_item;
  55.  
  56.  
  57.  
  58. class partition {
  59.  
  60. virtual void clear_inf(ent&) const {}
  61.  
  62. partition_item used_items;                 // List of used partition items
  63.  
  64. public:  // operations 
  65.  
  66. void  union_blocks(partition_item,partition_item);
  67. partition_item find(partition_item);
  68.  
  69. partition_item make_block(ent x = nil) 
  70. { used_items = new partition_node(x,used_items); 
  71.   return used_items; 
  72.  }
  73.  
  74. int  same_block(partition_item a, partition_item b) 
  75. { return find(a)==find(b); }
  76.  
  77. ent   inf(partition_item a) { return find(a)->info; }
  78.  
  79. void  set_inf(partition_item a, ent x) { find(a)->info = x; }
  80.  
  81. void clear();                      // deletes all used items
  82.  
  83.  partition() { used_items = 0; }   // constructor
  84. ~partition() { clear();  }         // destructor 
  85.  
  86. };
  87.  
  88.  
  89. //------------------------------------------------------------------------------
  90. // PARTITION  (named partitions)
  91. //-----------------------------------------------------------------------------
  92.  
  93. #define PARTITION(type) name2(type,PARTITION)
  94.  
  95. #define PARTITIONdeclare(type)\
  96. \
  97. struct PARTITION(type) : public partition {\
  98. \
  99. void clear_inf(ent& x) const { Clear(*(type*)&x); }\
  100. \
  101. partition_item make_block(type x) { return partition::make_block(Ent(x)); }\
  102. \
  103. type  inf(partition_item a) { return (type)partition::inf(a); }\
  104. \
  105. void  set_inf(partition_item a, type x) { partition::set_inf(a,Ent(x)); }\
  106. \
  107.  PARTITION(type)() {}\
  108. ~PARTITION(type)() {}\
  109. };
  110.  
  111.  
  112. #endif
  113.